import java.util.Arrays;


public class Diferencia {

	/**
	 * @param args
	 */
	
	public static int[] a;
	
	/**
	 * Forma recursiva del problema
	 * 
	 * 
	 * @param i la suma que se busca obtener con  los elementos del sub conjunto
	 * @param j existe un subconjunto con los elmentos del 0 al j
	 * @return si existe un subconjunto que tome los elementos del 0 al j que sume la cantidad i 
	 */
	public static boolean existe(int i , int j ){
		if (i<0)return false;
		if(j==0)return true;
		return existe(i-1,j)||existe(i-1,j-a[i]);
	}

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int sum=0;
		int n=5;
		a=new int[]{30, 49, 32, 28, 11};
		for (int i = 0; i < a.length; i++) 
			sum+=a[i];
		
		int tem=Integer.MAX_VALUE;
		int s1=-1;
		int obj=(sum/2);
		boolean[][] memo=new boolean[obj+1][n];
		
		//Iniciando casos base de la recursion
		for (int i = 0; i < n; i++){
			memo[0][i]=true;
		}
		//llenando la matrix para si existe o no el elmento
		for (int i = 1; i <= obj; i++) {
			for (int j = 1; j < n; j++) {
				memo[i][j]=i-a[j]>=0?memo[i-a[j]][j-1]:false||memo[i][j-1];
			}
		}

		//Selecionando un subconjunto cuya suma sea lo mas servana al al objetivo
		for (int i = obj; i >= 1; i--){
				if(memo[i][n-1]&&tem>(obj-i)){
					tem=obj-i;
					s1=i;
				}
		}
		System.out.println(Math.abs(s1-(2*obj-s1)));
		
	}
	
	
	

}
